package org.example.tree;

import java.text.SimpleDateFormat;
import java.util.Arrays;
import java.util.Date;

public class HeapSort {

    public static void main(String[] args) {
        /*int arr[] = {4,6,8,5,9,-1,-3};
        heapSort(arr);*/
        int[] arr = new int[8000000];
        for (int i = 0; i < 8000000; i++) {
            arr[i] = (int) (Math.random() * 8000000); // 生成一个[0, 8000000) 数
        }

        System.out.println("排序前");
        Date data1 = new Date();
        SimpleDateFormat simpleDateFormat = new SimpleDateFormat("yyyy-MM-dd HH:mm:ss");
        String date1Str = simpleDateFormat.format(data1);
        System.out.println("排序前的时间是=" + date1Str);

        heapSort(arr);

        Date data2 = new Date();
        String date2Str = simpleDateFormat.format(data2);
        System.out.println("排序前的时间是=" + date2Str);
        //花费两秒

    }

    public static void heapSort(int arr[]){

        int temp = 0;
        //先让整个数组符合堆排序
        for (int i = arr.length/2 -1; i >= 0; i--){
            adjustHeap(arr,i,arr.length);
        }
        /*
		 * 2).将堆顶元素与末尾元素交换，将最大元素"沉"到数组末端;
　　		   3).重新调整结构，使除了最后一个元素的其他元素满足堆定义，
           然后继续交换堆顶元素与当前末尾元素，反复执行调整+交换步骤，直到整个序列有序。
		 */
        for (int j = arr.length-1; j>0; j--){
            temp = arr[j];
            arr[j] = arr[0];
            arr[0] = temp;
            adjustHeap(arr,0,j);
        }
        //System.out.println(Arrays.toString(arr));

    }

    /**
     *  功能： 完成将以i对应的非叶子节点的树调整成大顶堆
     * @param arr 待调整的数组
     * @param i 表示非叶子节点在数组中的索引
     * @param length 表示对多少个元素继续调整，length 实在逐渐减少
     */
    public static void adjustHeap(int arr[], int i, int length){

        int temp = arr[i];
        //1.k = i*2 +1 表示k是i节点的左子节点
        for (int k = i*2 + 1; k<length; k = k*2 + 1){
            //如果k小于数组长度及左节点小于右节点
            if (k < length -1 && arr[k] < arr[k+1]){
                k++;
            }
            //拿左右节点中最大一个节点根父节点比较
            if (arr[k] > temp){
                 arr[i] = arr[k];
                 i = k;
            }else{
                break;
            }
        }
        //当for循环结束后，已经将i为父节点的树的最大值放在了顶部
        arr[i] = temp;
    }

}
